#ifndef _TREE_H_
#define _TREE_H_

#include <stdlib.h>

struct TreeNode;
typedef struct TreeNode *Tree;
typedef int Data;

struct TreeNode {
    Tree left;
    Tree right;
    Data data;
};

typedef int (*Comp)(Data, Data);
typedef void (*Visit)(Tree);

int intcomp(Data left, Data right)
{
    return left - right;
}

void intprint(Tree node)
{
    printf("%d", node->data);
}

Tree tree_create(Data da)
{
    Tree root = (Tree)malloc(sizeof(struct TreeNode));
    root->left = NULL;
    root->right = NULL;
    root->data = da;
    return root;
}

Tree tree_insert(Tree root, Data da, Comp comp)
{
    if (root == NULL) {
        root = (Tree)malloc(sizeof(struct TreeNode));
        root->left = NULL;
        root->right = NULL;
        root->data = da;
        return root;
    }

    while (root != NULL) {
        if (comp(da, root->data) < 0) {
            if (root->left == NULL) {
                root->left = tree_create(da);
                return root->left;
            }

            root = root->left;
        } else if (comp(da, root->data) > 0) {
            if (root->right == NULL) {
                root->right = tree_create(da);
                return root->right;
            }

            root = root->right;
        } else {
            return root;
        }
    }
}

Tree tree_find(Tree root, Data da, Comp comp)
{
    if (root == NULL) {
        return NULL;
    }

    while (root != NULL) {
        if (comp(da, root->data) < 0) {
            root = root->left;
        } else if (comp(da, root->data) > 0) {
            root = root->right;
        } else {
            return root;
        }
    }

    return root;
}

void tree_print(Tree root, Visit vi)
{
    if (root != NULL) {
        tree_print(root->left, vi);
        vi(root);
        printf(" ");
        tree_print(root->right, vi);
    }
}

#endif
